package com.zjsru.oneDay202205;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: likew
 * @Date: 2022/5/7
 *
 * 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
 * 最小基因变化
 * 输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
 * 输出：1
 *
 * 输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
 * 输出：3
 *
 */
public class minMutation {
    static char[] items = new char[]{'A', 'C', 'G', 'T'};
    public int minMutation(String start, String end, String[] bank) {
        Set<String> set = new HashSet<>();
        for (String s: bank) set.add(s);
        Deque<String> d = new ArrayDeque<String>();
        Map<String,Integer> map = new HashMap<>();
        d.addLast(start);
        map.put(start,0);
        while(!d.isEmpty()){
            int size = d.size();
            while(size-- > 0){
                String s = d.pollFirst();
                char[] cs = s.toCharArray();
                int step = map.get(s);
                for (int i = 0; i < 8; i++) {
                    for (char c: items) {
                        if(cs[i] == c) continue;
                        char[] clone = cs.clone();
                        clone[i] = c;
                        String sub = String.valueOf(clone);
                        if(!set.contains(sub)) continue;;
                        if(map.containsKey(sub)) continue;
                        if(sub.equals(end)) return step + 1;
                        map.put(sub,step + 1);
                        d.addLast(sub);
                    }
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        minMutation minMutation = new minMutation();
        String start = "AACCGGTT";
        String end = "AACCGGTA";
        String[] bank = new String[]{"AACCGGTA"};
        System.out.println(minMutation.minMutation(start, end, bank));
    }
}
